package com.leetcode.algorithm.y22.m08.w3;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 257. 二叉树的所有路径
 * 
 * https://leetcode.cn/problems/binary-tree-paths/
 * 
 * @author jie.deng
 *
 */
class Question0257Solution01 {

	public List<String> binaryTreePaths(TreeNode root) {
		List<String> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		Deque<Integer> queue = new ArrayDeque<>();
		dfs(root, result, queue);
		return result;
	}

	// DFS 先序遍历
	// 从根节点到叶子节点的路径
	private void dfs(TreeNode node, List<String> result, Deque<Integer> queue) {
		// 递归终止条件
		if (node.left == null && node.right == null) {
			StringBuilder builder = new StringBuilder();
			Iterator<Integer> iter = queue.iterator();
			while (iter.hasNext()) {
				builder.append(iter.next());
				builder.append("->");
			}
			builder.append(node.val);
			result.add(builder.toString());
			return;
		}

		// 当前层逻辑
		queue.offerLast(node.val);

		// 递归调用
		if (node.left != null) {
			dfs(node.left, result, queue);
		}
		if (node.right != null) {
			dfs(node.right, result, queue);
		}

		// 回溯
		queue.pollLast();
	}

}